package main

import "fmt"

// 146 LRU 缓存 https://leetcode.cn/problems/lru-cache‘
// 带头结点的双向链表
// 初始化的时候 头指向尾 尾指向头

func main() {
	var v int
	instance := Constructor(2)
	instance.Put(1, 1)
	instance.Put(2, 2)
	v = instance.Get(1)
	fmt.Println(v)
	instance.Put(3, 3)
	v = instance.Get(2)
	fmt.Println(v)
}

type cacheNode struct {
	prev *cacheNode
	next *cacheNode
	val  int
	key  int
}

type LRUCache struct {
	dbMap map[int]*cacheNode
	head  *cacheNode //头 - 旧的 删除从这里
	tail  *cacheNode //尾 - 新的 添加从这里
	c     int        //最大数量
}

func Constructor(capacity int) LRUCache {
	instance := LRUCache{
		dbMap: make(map[int]*cacheNode, capacity),
		head:  &cacheNode{},
		tail:  &cacheNode{},
		c:     capacity,
	}
	instance.head.next = instance.tail
	instance.tail.prev = instance.head
	return instance
}

func (this *LRUCache) Get(key int) int {
	v, ok := this.dbMap[key]
	if !ok {
		return -1
	}
	// 放到最后
	this.delete(v)
	this.addToTail(v)
	return v.val
}

func (this *LRUCache) Put(key int, value int) {
	v, ok := this.dbMap[key]
	if ok {
		// 已经存在
		v.val = value
		this.delete(v)
		this.addToTail(v)
		return
	}
	if len(this.dbMap) >= this.c {
		this.delete(this.head.next)
	}
	// 放到最后
	node := &cacheNode{key: key, val: value}
	this.addToTail(node)
	return
}

func (this *LRUCache) delete(node *cacheNode) {
	delete(this.dbMap, node.key)
	node.next.prev = node.prev
	node.prev.next = node.next
}

func (this *LRUCache) addToTail(node *cacheNode) {
	node.prev = this.tail.prev
	node.prev.next = node
	node.next = this.tail
	this.tail.prev = node
	this.dbMap[node.key] = node
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
